\documentclass[submission]{FPSAC2017}

\articlenumber{30}
\addbibresource{30_Hopkins_McConville_Propp.bib}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} 

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{question}[thm]{Question}
\newtheorem{fact}[thm]{Fact}
\newtheorem{obs}[thm]{Observation}

\newtheorem{Definition}[thm]{Definition}
\newenvironment{definition}
  {\begin{Definition}\rm}{\end{Definition}}

\newtheorem{Example}[thm]{Example}
\newenvironment{example}
  {\begin{Example}\rm}{\end{Example}}
  
\newtheorem{Remark}[thm]{Remark}
\newenvironment{remark}
  {\begin{Remark}\rm}{\end{Remark}}
  
\numberwithin{equation}{section}

\usepackage{lipsum}

\usepackage{graphicx}  
%\usepackage{tikz}
%\usetikzlibrary{decorations.pathreplacing}
%\usepackage{tkz-graph}
%\usepackage[all]{xy}
%\usetikzlibrary{arrows}
%\usetikzlibrary{decorations.markings}

%\usetikzlibrary{arrows.meta}

%\def\SetFancyGraph {
%	\SetVertexMath
%	\GraphInit[vstyle=Art]
%	\SetUpVertex[MinSize=2pt]
%	\SetVertexLabel
%	\tikzset{VertexStyle/.style = {shape = circle,shading = ball,ball color = black,inner sep = 1.5pt}}
%	\SetUpEdge[color=black]
%	\tikzset{>={Latex[width=2mm,length=2mm]}}
%	\tikzset{->-/.style={decoration={ markings, mark=at position 0.8 with {\arrow{>}}},postaction={decorate}}}
%	\tikzset{->--/.style={decoration={ markings, mark=at position 0.55 with {\arrow{>}}},postaction={decorate}}}
%}

%\usetikzlibrary{external}
%\tikzexternalize


\title{Sorting via chip-firing}

\author{Sam Hopkins\addressmark{1}, Thomas McConville\addressmark{1} \and James Propp\addressmark{2}}

\address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA \\ \addressmark{2}Department of Mathematical Sciences, University of Massachusetts, Lowell, MA\\}

\received{\today}

\abstract{We investigate a variant of the chip-firing process on the infinite path graph~$\mathbb{Z}$: rather than treating the chips as indistinguishable, we label them with positive integers.  To fire an unstable vertex, i.e.\ a vertex with more than one chip, we choose any two chips at that vertex and move the lesser-labeled chip to the left and the greater-labeled chip to the right.  This labeled version of the chip-firing process exhibits a remarkable confluence property, similar to but subtler than the confluence that prevails for unlabeled chip-firing: when all chips start at the origin and the number of chips is even, the chips always end up in sorted order.  Our proof of sorting relies upon an independently interesting lemma concerning unlabeled chip-firing which says that stabilization preserves a natural partial order on configurations. We also discuss extensions to other variants of the infinite path, an intriguing empirical observation on random firing of labeled chips, and a possible generalization to other types.}

\keywords{chip-firing, abelian sandpile model, confluence}


\begin{document}

\maketitle

\section{Introduction}

We introduce a labeled version of the chip-firing process. The chip-firing process is a discrete dynamical system that takes place on a graph. The name ``chip-firing'' was coined by Bj\"{o}rner, Lov\'asz, and Shor~\cite{bjorner1991chip}, but in fact this process is essentially the same as the abelian sandpile model (ASM) introduced by Bak, Tang, and Wiesenfeld~\cite{bak1987self} and further developed by Dhar~\cite{dhar1990self,dhar1999abelian}. (See also the work of Engel~\cite{engel1976why}.) Here ``abelian'' means that the order in which certain local moves are carried out has no effect on the final state. This property is also often called ``confluence'' in the context of abstract rewriting systems. Dhar views the ASM as a prototype for networks of communicating processors that achieve predictable results despite a lack of global synchronization; this point of view has been developed by Levine and his coauthors~\cite{bond2016abelian1,bond2016abelian2,bond2016abelian3,holroyd2015abelian}, who introduced a broad family of such networks, called ``abelian networks,'' to which the ASM belongs.

Bj\"{o}rner, Lov\'asz, and Shor were directly inspired by papers of Spencer~\cite{spencer1986balancing} and Anderson et al.~\cite{anderson1989disks} that investigated chip-firing in the special case of the infinite path graph~$\mathbb{Z}$ (which has vertex set $\mathbb{Z}$ with $i$ and $j$ joined by an edge whenever $|i-j| = 1$). In fact, it is in exactly this special case of the infinite path graph~$\mathbb{Z}$ that we introduce labeled chip-firing. Here is how the labeled chip-firing process on $\mathbb{Z}$ works: we start with~$n$ labeled chips~$(1),(2),\ldots,(n)$ at the origin; at each step we choose any two chips~$(a)$ and~$(b)$ with $a < b$ that occupy the same vertex~$i$ and \emph{fire} these chips together, moving~$(a)$ to vertex~$i-1$ and $(b)$ to vertex~$i+1$; we keep carrying out firings until no chips can fire. For example, suppose $n=4$, so that we start from the following configuration (where we draw~$\mathbb{Z}$ in the plane as a number line in the usual way, with~$i-1$ to the left of $i$):
\begin{center}
%\tikzsetnextfilename{fig1}
%\begin{tikzpicture}[scale=1]
%	\SetFancyGraph
%	\Vertex[NoLabel,x=-4,y=0,empty]{-4}
%	\Vertex[NoLabel,x=-3,y=0]{-3}
%	\Vertex[NoLabel,x=-2,y=0]{-2}
%	\Vertex[NoLabel,x=-1,y=0]{-1}
%	\Vertex[NoLabel,x=0,y=0]{0}
%	\Vertex[NoLabel,x=1,y=0]{1}
%	\Vertex[NoLabel,x=2,y=0]{2}
%	\Vertex[NoLabel,x=3,y=0]{3}
%	\Vertex[NoLabel,x=4,y=0,empty]{4}
%	\Edges[style={thick}](-3,-2,-1,0,1,2,3)
%	\Edges[style={thick,dashed}](-4,-3)
%	\Edges[style={thick,dashed}](3,4)
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.4) {1};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.9) {2};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,1.4) {3};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,1.9) {4};
%\end{tikzpicture}
\includegraphics{fig1}
\end{center}
By firing chips~$(1)$ and~$(2)$ we reach the following configuration:
\begin{center}
%\tikzsetnextfilename{fig2}
%\begin{tikzpicture}[scale=1]
%	\SetFancyGraph
%	\Vertex[NoLabel,x=-4,y=0,empty]{-4}
%	\Vertex[NoLabel,x=-3,y=0]{-3}
%	\Vertex[NoLabel,x=-2,y=0]{-2}
%	\Vertex[NoLabel,x=-1,y=0]{-1}
%	\Vertex[NoLabel,x=0,y=0]{0}
%	\Vertex[NoLabel,x=1,y=0]{1}
%	\Vertex[NoLabel,x=2,y=0]{2}
%	\Vertex[NoLabel,x=3,y=0]{3}
%	\Vertex[NoLabel,x=4,y=0,empty]{4}
%	\Edges[style={thick}](-3,-2,-1,0,1,2,3)
%	\Edges[style={thick,dashed}](-4,-3)
%	\Edges[style={thick,dashed}](3,4)
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-1,0.4) {1};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (1,0.4) {2};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.4) {3};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.9) {4};
%\end{tikzpicture}
\includegraphics{fig2}
\end{center}
Then by firing~$(3)$ and~$(4)$ together we reach this configuration:
\begin{center}
%\tikzsetnextfilename{fig3}
%\begin{tikzpicture}[scale=1]
%	\SetFancyGraph
%	\Vertex[NoLabel,x=-4,y=0,empty]{-4}
%	\Vertex[NoLabel,x=-3,y=0]{-3}
%	\Vertex[NoLabel,x=-2,y=0]{-2}
%	\Vertex[NoLabel,x=-1,y=0]{-1}
%	\Vertex[NoLabel,x=0,y=0]{0}
%	\Vertex[NoLabel,x=1,y=0]{1}
%	\Vertex[NoLabel,x=2,y=0]{2}
%	\Vertex[NoLabel,x=3,y=0]{3}
%	\Vertex[NoLabel,x=4,y=0,empty]{4}
%	\Edges[style={thick}](-3,-2,-1,0,1,2,3)
%	\Edges[style={thick,dashed}](-4,-3)
%	\Edges[style={thick,dashed}](3,4)
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-1,0.4) {1};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (1,0.4) {2};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-1,0.9) {3};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (1,0.9) {4};
%\end{tikzpicture}
\includegraphics{fig3}
\end{center}
After firing~$(1)$ and~$(3)$, and then firing~$(2)$ and~$(4)$, in two more steps we reach the following configuration:
\begin{center}
%\tikzsetnextfilename{fig4}
%\begin{tikzpicture}[scale=1]
%	\SetFancyGraph
%	\Vertex[NoLabel,x=-4,y=0,empty]{-4}
%	\Vertex[NoLabel,x=-3,y=0]{-3}
%	\Vertex[NoLabel,x=-2,y=0]{-2}
%	\Vertex[NoLabel,x=-1,y=0]{-1}
%	\Vertex[NoLabel,x=0,y=0]{0}
%	\Vertex[NoLabel,x=1,y=0]{1}
%	\Vertex[NoLabel,x=2,y=0]{2}
%	\Vertex[NoLabel,x=3,y=0]{3}
%	\Vertex[NoLabel,x=4,y=0,empty]{4}
%	\Edges[style={thick}](-3,-2,-1,0,1,2,3)
%	\Edges[style={thick,dashed}](-4,-3)
%	\Edges[style={thick,dashed}](3,4)
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-2,0.4) {1};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.4) {2};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (0,0.9) {3};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (2,0.4) {4};
%\end{tikzpicture}
\includegraphics{fig4}
\end{center}
Finally, by firing~$(2)$ and~$(3)$ we reach the following \emph{stable} configuration, which has no more possible firings:
\begin{center}
%\tikzsetnextfilename{fig5}
%\begin{tikzpicture}[scale=1]
%	\SetFancyGraph
%	\Vertex[NoLabel,x=-4,y=0,empty]{-4}
%	\Vertex[NoLabel,x=-3,y=0]{-3}
%	\Vertex[NoLabel,x=-2,y=0]{-2}
%	\Vertex[NoLabel,x=-1,y=0]{-1}
%	\Vertex[NoLabel,x=0,y=0]{0}
%	\Vertex[NoLabel,x=1,y=0]{1}
%	\Vertex[NoLabel,x=2,y=0]{2}
%	\Vertex[NoLabel,x=3,y=0]{3}
%	\Vertex[NoLabel,x=4,y=0,empty]{4}
%	\Edges[style={thick}](-3,-2,-1,0,1,2,3)
%	\Edges[style={thick,dashed}](-4,-3)
%	\Edges[style={thick,dashed}](3,4)
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-2,0.4) {1};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (-1,0.4) {2};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (1,0.4) {3};
%	\node [circle,draw,thick,inner sep=0,minimum size=12pt] at (2,0.4) {4};
%\end{tikzpicture}
\includegraphics{fig5}
\end{center}
In this process we made several arbitrary choices of which pairs of chips to fire. As it turns out, no matter what choices we made we would have always reached this same stable configuration where the chips appear in sorted order from left to right. This is a confluence result which says that the divergent paths our process can take must at some later point come back together. It is well known that confluence holds for the unlabeled chip-firing process (on any graph and for any configuration with sufficiently few chips to guarantee that stabilization is possible at all): this is one of the basic results of~\cite{bjorner1991chip}. But confluence for the labeled chip-firing process is much subtler. Indeed, not all initial configurations are confluent in the labeled chip-firing process. This means in particular that the theory of abelian networks does not automatically apply to our situation. To see that not all initial configurations are confluent, consider the configuration that has three chips at the origin rather than four. We can fire~$(1)$ and~$(2)$, or fire~$(1)$ and~$(3)$, or fire~$(2)$ and~$(3)$; in all three cases, the result is a stable configuration, but the labeled chips end up at different vertices, so confluence does not hold in this case. More generally, if we start with an \emph{odd} number of labeled chips at~$0$, we can make sure that any preselected chip never moves away from~$0$, so confluence does not hold. Our main result, proved in the next section, says that the labeled chip-firing process on $\mathbb{Z}$ is confluent, and in particular sorts the chips, as long as the number of chips is \emph{even}.

\section{Main result}

One of the main ways we will understand this labeled chip-firing process is by relating it to the usual unlabeled chip-firing process. Therefore, we first review unlabeled chip-firing on the graph $\mathbb{Z}$.  A \emph{configuration of unlabeled chips} on $\mathbb{Z}$ is some assignment of a finite number of indistinguishable chips to the vertices of $\mathbb{Z}$. All configurations, both labeled and unlabeled, will be on $\mathbb{Z}$ in what follows in this section. We use lowercase letters for unlabeled configurations. Formally, we treat an unlabeled configuration $c$ as a function $c \colon \mathbb{Z} \to \mathbb{N}$ with $\sum_i c(i) < \infty$ and we think of $c$ as having $c(i)$ chips at~$i$. We use $\mathrm{supp}(c)$ to denote the \emph{support} of $c$, i.e., $\mathrm{supp}(c) := \{i \in \mathbb{Z}\colon c(i) \geq 1\}$. We write $\mathrm{max}(c) := \mathrm{max}(\mathrm{supp}(c))$ and $\mathrm{min}(c) := \mathrm{min}(\mathrm{supp}(c))$. As is customary, we use the convention~$\mathrm{max}(\varnothing) := -\infty$ and~$\mathrm{min}(\varnothing) := \infty$.  If $c$ is a configuration and~$i \in \mathbb{Z}$ is some vertex such that~$c$ has at least two chips at $i$, we may perform a \emph{chip-firing move} at $i$, which moves one chip at~$i$ leftward one vertex and one chip at~$i$ rightward one vertex. If the resulting configuration is $c'$ then in this case we also say that $c'$ is obtained from~$c$ by \emph{firing at vertex~$i$}. We write~$c \to d$ to mean that $d$ is obtained from~$c$ by some sequence of (zero or more) chip-firing moves. We say $c$ is \emph{stable} if we cannot perform any chip-firing moves on $c$, that is, if~$c \to d$ implies that~$c=d$. Of course, the map~$c \mapsto \mathrm{supp}(c)$ is a bijection between stable configurations of
 $n$ chips and subsets of~$\mathbb{Z}$ of size~$n$. 

The following confluence property of the chip-firing process is well known; for instance, it can be deduced from the main results of~\cite{bjorner1991chip}. It was also proved in a special case (\cref{lem:deltastab} below) by Anderson et al.~\cite{anderson1989disks}, but the proof in general is more or less the same as in that special case. At any rate, it is essentially a consequence of Newman's lemma~\cite{newman1942theories} (a.k.a.~the diamond lemma) which says that ``local confluence'' is enough to imply confluence for terminating systems.

\begin{lemma} \label{lem:stab}
For any configuration $c$, there is a unique stable $d$ with $c \to d$.
\end{lemma}

We use $\widetilde{c}$ to denote the \emph{stabilization} of $c$, i.e.~the unique stable~$d$ with $c \to d$ guaranteed by \cref{lem:stab}. A fact (which follows immediately from \cref{lem:stab}) that we will use over and over again is that if $c \to d$ then $\widetilde{d} = \widetilde{c}$.

Let us introduce some notation for specific configurations of unlabeled chips. For two configurations~$c$ and~$d$, let us use~$c+d$ to denote their \emph{sum}, i.e., the configuration with $(c+d)(i) = c(i) + d(i)$ for all~$i \in \mathbb{Z}$. It is clear that if $c \to c'$ then $c + d \to c' + d$. For~$n \in \mathbb{N}$ and a configuration $c$, we use the shorthand $nc := \overbrace{c + c + \cdots c}^{n \textrm{ terms }}$. For $i \in \mathbb{Z}$ we let $\delta_i$ denote the configuration that has a single chip at $i$ and no other chips; in other words, $\delta_i$ is the unique stable configuration with $\mathrm{supp}(\delta_i) = \{i\}$. For $i,j \in \mathbb{Z}$, we let~$\delta_{[i,j]}$ denote the configuration that has one chip at vertex~$k$ for all $i \leq k \leq j$ and no other chips; in other words $\delta_{[i,j]}$ is the unique stable configuration with $\mathrm{supp}(\delta_{[i,j]}) = [i,j]$. (We use the convention that if $i > j$ then $[i,j] = \varnothing$.) Note that $\delta_i = \delta_{[i,i]}$.

We now describe some formulas for specific stabilizations that will be needed later.

\begin{prop} \label{prop:linestab}
Suppose that $c = \delta_{[a+1,b-1]} + \delta_i$, where $a,b,i \in \mathbb{Z}$ satisfy $a < b$, $a \leq i$, and~$i \leq b$. Then we have~$\widetilde{c} = \delta_{[a,a+b-i-1]} + \delta_{[a+b-i+1,b]}$.
\end{prop}
\begin{proof}
We prove this by induction on $b-a$. If $b-a=1$ the proposition is clear because then $c = \widetilde{c} = \delta_i$. So assume $b-a>1$ and the result is known for smaller values of~$b-a$. If $i=a$ or $i=b$ the proposition is also clear because then $c = \widetilde{c}$. So assume that~$a < i < b$. Set $c' := \delta_{[a+1,i-1]} + \delta_{i-1}$ and $c'' := \delta_{i+1} + \delta_{[i+1,b-1]}$. By firing at vertex~$i$ we see that~$c \to c' + c''$. Applying the inductive hypothesis gives
\begin{align*}
\widetilde{c'} &= \delta_a + \delta_{[a+2,i]}, \\
\widetilde{c''} &= \delta_{[i,b-2]} + \delta_b.
\end{align*}
So $c \to \delta_a + \delta_{[a+2,i]} + \delta_{[i,b-2]} + \delta_b = \delta_a + c''' + \delta_b$ where $c''' := \delta_{[a+2,b-2]} + \delta_i$. Applying the inductive hypothesis again gives
\[ \widetilde{c'''} = \delta_{[a+1,a+b-i-1]} + \delta_{[a+b-i+1,b-1]}, \]
so that $c \to \delta_{[a,a+b-i-1]} + \delta_{[a+b-i+1,b]}$. But $\delta_{[a,a+b-i-1]} + \delta_{[a+b-i+1,b]}$ is stable, which means we must have~$\widetilde{c} = \delta_{[a,a+b-i-1]} + \delta_{[a+b-i+1,b]}$.
\end{proof}

The unlabeled configuration we are most interested in is $n\delta_0$. The following description of the stabilization of $n\delta_0$ is also well known, appearing for instance in the original paper of Anderson et al.~\cite{anderson1989disks}. For completeness we provide a short proof of this lemma using the previous proposition.

\begin{lemma} \label{lem:deltastab}
For all $n \geq 1$ we have,
\[\widetilde{n\delta_0} = \begin{cases} \delta_{[-m,-1]} + \delta_{[1, m]} &\textrm{if $n=2m$ is even};\\
\delta_{[-m, m]} &\textrm{if $n=2m+1$ is odd}.\end{cases}\]
\end{lemma}

\begin{proof}
The proof is by induction on $n$. The case $n=1$ is clear; so suppose~$n>1$ and the result is known for $n-1$. Set $c:=\widetilde{(n\hspace{-0.1cm}-\hspace{-0.1cm}1)\delta_0}$. We have~$\widetilde{n\delta_0} = \widetilde{c+\delta_0}$. If $n=2m$ is even then by induction~$\widetilde{c} = \delta_{[-(m-1),m-1]}$, so~$\widetilde{c+\delta_0} =  \delta_{[-m,-1]} + \delta_{[1, m]}$ by \cref{prop:linestab}. If $n = 2m+1$ is odd, then by induction we have~$\widetilde{c} = \delta_{[-m,-1]} + \delta_{[1,m]}$ and so clearly we have~$\widetilde{c+\delta_0} = c = [-m,m]$.
\end{proof}

Now let us describe labeled chip-firing. A \emph{labeled configuration of chips} on~$\mathbb{Z}$ is some assignment of a finite number of distinguishable chips, labeled by positive integers, to the vertices of~$\mathbb{Z}$. We use uppercase calligraphic script for labeled configurations and use $(i)$ to denote the chip labeled $i$. Formally, we treat a labeled configuration~$\mathcal{C}$ as a function~$\mathcal{C}\colon X \to \mathbb{Z}$ for some $X \subseteq \mathbb{Z}_{>0}$, and we think of chip~$(i)$ as being at the vertex~$\mathcal{C}(i)$ in $\mathcal{C}$ for all~$i \in X$. Normally we will take $X = [n]$ and thus study labeled configurations of the $n$ chips~$(1),(2),\ldots,(n)$.  If $a < b$ and chips $(a)$ and $(b)$ are at the same vertex in $\mathcal{C}$, we may \emph{fire}~$(a)$ and~$(b)$ together in $\mathcal{C}$ by moving~$(a)$ leftward one vertex and~$(b)$ rightward one vertex. (The important point is that {\bf chips with lesser labels move leftward}.)  We write~$\mathcal{C} \to \mathcal{D}$ to mean that $\mathcal{D}$ is obtained from~$\mathcal{C}$ by a sequence of labeled chip-firing moves of this form. If $\mathcal{C}$ is a labeled configuration we use~$[\mathcal{C}]$ to denote the underlying unlabeled configuration: thus $[\mathcal{C}](i) := \#\mathcal{C}^{-1}(i)$ for all~$i \in \mathbb{Z}$.  We say that~$\mathcal{D}$ is \emph{stable} if~$[\mathcal{D}]$ is stable. As mentioned, our strategy in understanding labeled chip-firing will be to relate it to unlabeled chip-firing. To that end, here are some very basic facts relating labeled and unlabeled chip-firing, which we will use without even citing specifically from now on.

\begin{prop}~\,
\begin{itemize}
\item If $\mathcal{C} \to \mathcal{D}$ then $[\mathcal{C}] \to [\mathcal{D}]$.
\item If $c \to d$ and $c = [\mathcal{C}]$, then there exists $\mathcal{D}$ with $\mathcal{C} \to \mathcal{D}$ such that $d = [\mathcal{D}]$.
\end{itemize}
Consequently, for any $\mathcal{C}$ there is some stable $\mathcal{D}$ with $\mathcal{C} \to \mathcal{D}$, and we have $[\mathcal{D}] = \widetilde{[\mathcal{C}]}$.
\end{prop}

There need not be a unique stable $\mathcal{D}$ with $\mathcal{C} \to \mathcal{D}$: the previous proposition only determines~$[\mathcal{D}]$ but not the way that the chips are labeled in~$\mathcal{D}$. Nevertheless we are interested in cases where we do have a unique labeled stabilization. In particular, we will consider the labeled analog of $n\delta_0$, which has chips~$(1),(2),\ldots,(n)$ at vertex $0$ and no other chips; we denote this configuration by $\Delta^n$. In other words, $\Delta^n(i) := 0$ for all~$i \in [n]$. Of course,~$[\Delta^n] = n\delta_0$. Note, as mentioned in the introduction, that $\Delta^3$ already does not have a unique stabilization. On the other hand, our main result is that when~$n$ is even, $\Delta^n$ does have a unique stabilization.

First let us observe that there is a useful global symmetry in this labeled chip-firing process when we start from the configuration~$\Delta^n$. If $\mathcal{C}$ is a configuration of $n$ labeled chips, define its \emph{dual}~$\mathcal{C}^{*}$ as follows: first reflect $\mathcal{C}$ horizontally about the vertex~$0$, then replace chip $(i)$ by chip $(n+1-i)$ for all $1 \leq i \leq n$. Of course, $(\mathcal{C}^{*})^{*} = \mathcal{C}$.

\begin{lemma} \label{lem:symmetry}
We have $\Delta^n \to \mathcal{C}$ if and only if $\Delta^n \to \mathcal{C}^{*}$.
\end{lemma}
\begin{proof}
It is easy to see that the duality operation respects labeled chip-firing moves, meaning that if $\mathcal{D}$ is obtained from $\mathcal{C}$ by a labeled chip-firing move then $\mathcal{D}^{*}$ is obtained from $\mathcal{C}^{*}$ by a labeled chip-firing move. The lemma then follows since~$(\Delta^n)^* = \Delta^n$.
\end{proof}

Very roughly speaking, to prove confluence of the labeled chip-firing process we study how far we can move chips via chip-firing. The following is obvious but important. 

\begin{prop}~ \label{prop:stabmaxineq}
If $c \to d$ then $\mathrm{min}(\widetilde{c}) \leq \mathrm{min}(d)$.
\end{prop}
\begin{proof}
Each chip-firing move preserves or decreases the minimum occupied vertex, so we have $\mathrm{min}(d') \leq \mathrm{min}(d)$ for any $d \to d'$. Thus in particular we have $\mathrm{min}(\widetilde{d}) \leq \mathrm{min}(d)$. But if $c \to d$, then $\widetilde{d} = \widetilde{c}$.
\end{proof}

Applying \cref{prop:stabmaxineq} to our situation of interest tells us that if~$\Delta^n \to \mathcal{C}$ then we have~$\mathrm{min}([\mathcal{C}]) \geq  -\lfloor n/2\rfloor$ and, by \cref{lem:symmetry}, $\mathrm{max}([\mathcal{C}]) \leq \lfloor n/2\rfloor$. This puts some constraint on the movement of chips during the labeled chip-firing process, but is not really so useful because it says nothing about the position of chips with particular labels. We want to strengthen this conclusion about how far chips can move to take into account chip labels. 

First let us define some notion for restricting labeled configurations to a subset of chips. For a labeled configuration $\mathcal{C}$ with label set~$X$ and $Y \subseteq \mathbb{Z}_{>0}$, we use~$\mathcal{C} \setminus Y$ to denote the restriction of $\mathcal{C}$ to the chips with labels in~$X \setminus Y$. For any labeled configuration~$\mathcal{C}$ and any~$k \in \mathbb{N}$, we use the shorthand $\mathcal{C}|_{\geq k} := \mathcal{C} \setminus \{1,2,\ldots,k-1\}$. We want some way to describe how the largest-labeled chips evolve in the labeled chip-firing process. So let us say that an unlabeled configuration $d$ is \emph{rightward-reachable} from an unlabeled configuration~$c$, written~$c \xrightarrow{R} d$, if $d$ is obtained from~$c$ by a sequence of (zero or more) moves of the forms:
\begin{itemize}
\item perform a chip-firing move;
\item move one chip rightward one vertex.
\end{itemize}
This notion precisely captures the way the largest-labeled chips evolve under labeled chip-firing. Namely, we have the following.

\begin{prop} \label{prop:labeledrightaccess}
If $\mathcal{C} \to \mathcal{D}$ then $[\mathcal{C}|_{\geq k}] \xrightarrow{R} [\mathcal{D}|_{\geq k}]$.
\end{prop}
\begin{proof}
Suppose we fire two chips~$(a)$ and~$(b)$ in $\mathcal{C}$: if $a,b < k$, that firing does not affect~$[\mathcal{C}|_{\geq k}]$; if $k \leq a,b$, that firing  corresponds to a firing in $[\mathcal{C}|_{\geq k}]$; and if $a < k \leq b$, then that firing corresponds to moving a chip rightward in  $[\mathcal{C}|_{\geq k}]$.
\end{proof}

We want a strengthening of \cref{prop:stabmaxineq} that applies to rightward-reachability. To that end, we define a partial order on unlabeled configurations of $n$ chips that can informally be thought of as ``$c \leq d$ means $d$ is obtained from $c$ by moving chips rightward''; it is defined formally as follows. If $c$ and $d$ are configurations of~$n$ unlabeled chips on~$\mathbb{Z}$, we write $c \leq d$ if and only if~$\sum_{i \geq j}c(i) \leq \sum_{i \geq j}d(i)$ for all~$j \in \mathbb{Z}$. Observe that $c \leq d$ implies that $\mathrm{max}(c) \leq \mathrm{max}(d)$ and $\mathrm{min}(c) \leq \mathrm{min}(d)$. We write $c \lessdot d$ to mean that $d$ covers $c$ according to this partial order~$\leq$. In other words, $c \lessdot d$ means that $d$ is obtained from $c$ by moving one chip rightward one vertex. 

An important property of this partial order is that it is preserved under stabilization, as we establish right now. In fact, something even stronger is true: stabilization preserves the cover relations of this partial order. (Note that $c \mapsto \sum_{i} i\cdot c(i)$ is a rank function for~$\leq$. It is easy to verify that chip-firing moves preserve~$\sum_{i} i\cdot c(i)$. So in fact stabilization being order-preserving is easily seen to be equivalent to it preserving cover relations.)

\begin{lemma} \label{lem:stabcover}
If $c \lessdot d$ then $\widetilde{c} \lessdot \widetilde{d}$.
\end{lemma}
\begin{proof}
That $c \lessdot d$ means there is some $c'$ and $i \in \mathbb{Z}$ such that $c = c' + \delta_i$ and $d = c' + \delta_{i+1}$. Define~$a := \mathrm{max}\{j \leq i\colon j \notin \mathrm{supp}(\widetilde{c'})\}$ and $b := \mathrm{min}\{j \geq i+1\colon j \notin \mathrm{supp}(\widetilde{c'})\}$. Thus there exists a configuration $c''$ such that $ \widetilde{c'} = c'' + \delta_{[a+1,b-1]}$ and $\mathrm{supp}(c'') \cap [a,b] = \varnothing$. \cref{prop:linestab} then implies
\begin{align*}
\widetilde{\widetilde{c'} + \delta_i} &= c'' +\delta_{[a,a+b-i-1]} + \delta_{[a+b-i+1,b]}, \\
\widetilde{\widetilde{c'} \hspace{-0.1cm} + \hspace{-0.1cm} \delta_{i+1}} &= c'' +\delta_{[a,a+b-i-2]} + \delta_{[a+b-i,b]}. 
\end{align*}
In particular, $\widetilde{\widetilde{c'} + \delta_i} \lessdot\widetilde{\widetilde{c'} \hspace{-0.1cm} + \hspace{-0.1cm} \delta_{i+1}} $. But $c = \widetilde{\widetilde{c'} + \delta_i}$ and $d=\widetilde{\widetilde{c'} \hspace{-0.1cm} + \hspace{-0.1cm} \delta_{i+1}}$, so the claim is proved.
\end{proof}

\cref{lem:stabcover} is the key lemma which allows us to establish confluence of labeled chip-firing. It is also interesting in its own right as a result purely concerning unlabeled chip-firing. We now apply \cref{lem:stabcover} to give a strengthening of \cref{prop:stabmaxineq} which applies to rightward-reachability.

\begin{cor} \label{cor:rightaccess}
If $c \xrightarrow{R} d$ then $\widetilde{c} \leq \widetilde{d}$ and consequently $\mathrm{min}(\widetilde{c}) \leq \mathrm{min}(d)$.
\end{cor}

\begin{proof}
Suppose $c \xrightarrow{R} d$. Thus there is some sequence~$c_0,c'_0,c_1,c'_1,\ldots,c_{\ell},c'_{\ell}$ of configurations with $c = c_0$ and $c'_{\ell} = d$ such that:
\begin{itemize}
\item $c_i \to c'_i$ for all $0 \leq i \leq \ell$;
\item $c'_{i-1} \lessdot c_i$ for all $1 \leq i \leq \ell$.
\end{itemize}
We claim that $ \widetilde{c} \leq \widetilde{c_i} = \widetilde{c'_i}$ for all $0 \leq i \leq \ell$. That $\widetilde{c_i} = \widetilde{c'_i}$ follows from $c_{i} \to c'_{i}$. So the crucial part of the claim is to show $\widetilde{c}\leq\widetilde{c_i}$. Clearly this holds for $i=0$ since by definition~$c_0 = c$. So assume $1 \leq i \leq \ell$ and $ \widetilde{c}\leq \widetilde{c_{i-1}}$. Because~$c'_{i-1} \lessdot c_i $, from \cref{lem:stabcover} we get that~$ \widetilde{c_{i-1}} = \widetilde{c'_{i-1}} \lessdot \widetilde{c_i}$. Together with~$\widetilde{c} \leq \widetilde{c_{i-1}}$ this implies~$\widetilde{c} \leq \widetilde{c_i}$. So the claim is proved by induction.  Taking $i=\ell$ in the claim gives~$\widetilde{c} \leq \widetilde{c'_{\ell}} $, which is to say~$\widetilde{c} \leq \widetilde{d}$. This implies $\mathrm{min}(\widetilde{c}) \leq \mathrm{min}(\widetilde{d})$. But $\mathrm{min}(\widetilde{d}) \leq \mathrm{min}(d)$ by \cref{prop:stabmaxineq}.
\end{proof}

Now we can apply \cref{cor:rightaccess} to restrict, based on their labels, how far chips can move in our situation of interest.

\begin{lemma} \label{lem:labeledchippos}
Suppose $\Delta^n \to \mathcal{C}$. Then~$-\lfloor (n+1-k)/2 \rfloor \leq \mathcal{C}(k) \leq \lfloor k/2 \rfloor$ for all~$1 \leq k \leq n$.
\end{lemma}
\begin{proof}
First we show $-\lfloor (n+1-k)/2 \rfloor \leq \mathcal{C}(k)$. By \cref{prop:labeledrightaccess}, $[\Delta^n|_{\geq k}] \xrightarrow{R} [C|_{\geq k}]$. Thus by \cref{cor:rightaccess}, $\mathrm{min}(\widetilde{[\Delta^n|_{\geq k}]}) \leq \mathrm{min}([C|_{\geq k}])$. But $[\Delta^n|_{\geq k}] = (n+1-k)\delta_0$, and so \cref{lem:deltastab} tells us that~$\mathrm{min}(\widetilde{[\Delta^n|_{\geq k}]}) = -\lfloor (n+1-k)/2\rfloor$. Thus indeed chip $(k)$ must be at or to the left of the vertex~$-\lfloor (n+1-k)/2\rfloor$. That $\mathcal{C}(k) \leq \lfloor k/2 \rfloor$ then follows via \cref{lem:symmetry}.
\end{proof}

We are now ready to prove the main theorem, which says that when the number $n$ of chips is even, the labeled chip-firing process on~$\mathbb{Z}$ necessarily sorts these chips. It can be shown that the number of firings in this process is $\Theta(n^3)$, so this procedure is not being offered as a practical way to sort.

\begin{thm} \label{thm:main}
Suppose $n := 2m$ is even and $\Delta^n \to \mathcal{D}$ where $\mathcal{D}$ is stable. Then for all~$1 \leq k \leq m$ we have that $\mathcal{D}(k) = -(m+1)+k$ and $\mathcal{D}(m+k) = k$.
\end{thm}

\begin{proof} 
Let $n =2m$ be even and let $\Delta^n \to \mathcal{D}$ with $\mathcal{D}$ stable. For all $1 \leq k \leq m$, the assertion that $\mathcal{D}(m+k) = k$ follows from $\mathcal{D}(m+1-k) = -k$ by \cref{lem:symmetry}. Thus we prove only that~$\mathcal{D}(k) = -(m+1)+k$ for all $1 \leq k \leq m$.

The proof is by induction on $k$. So let us first address the base case $k=1$. \cref{lem:labeledchippos} says that $\mathcal{D}(i) > -m$ for all $2 \leq i \leq n$. (Here we use crucially that $n=2m$ is even.) But on the other hand, we know thanks to \cref{lem:deltastab} that vertex $-m$ is occupied in $\mathcal{D}$. So in fact it must be occupied by chip~(1).

Now assume $k \geq 2$ and the result holds for all smaller values of~$k$. We will use some internal lemmas in the proof (``internal'' because they assume the inductive hypothesis).

\begin{lemma} \label{lem:prooflem1}
If $\mathcal{D}(k) > -(m+1)+k$ then for all~$1 \leq j \leq k-1$, chip $(k)$ never fired together with chip~$(j)$ in the labeled chip-firing process $\Delta^n \to \mathcal{D}$.
\end{lemma}
\begin{proof}
Suppose that $\mathcal{D}(k) > -(m+1)+k$. And suppose to the contrary that chip~$(k)$ did fire together with chip~$(j)$ for some $1 \leq j \leq k-1$ at some point in the labeled chip-firing process $\Delta^n \to \mathcal{D}$. Let us concentrate on the last moment when this happened: let~$\mathcal{C}'$ be the step before chip~$(k)$ fired with some chip~$(j)$ with $1 \leq j \leq k-1$ for the last time (and thus define $j$ to be the label of this other chip). Let $\mathcal{C}$ be the result of firing~$(k)$ and~$(j)$ together in $\mathcal{C}'$. So $\Delta^n \to \mathcal{C}'$, $\mathcal{C}$ is obtained from $\mathcal{C}'$ by firing~$(k)$ and~$(j)$ together, and $\mathcal{D}$ is obtained from $\mathcal{C}$ by a sequence of firings that either do not involve~$(k)$, or fire~$(k)$ together with a chip with a greater label. This implies that~$[\mathcal{C} \setminus \{k\}] \xrightarrow{R} [\mathcal{D} \setminus \{k\}]$ and \cref{cor:rightaccess} thus yields~$\widetilde{[\mathcal{C} \setminus \{k\}]} \leq [\mathcal{D} \setminus \{k\}]$. As a consequence of the assumptions that~$\mathcal{D}(k) > -(m+1)+k$ and that~$k \leq m$, together with \cref{lem:deltastab}, we have~$[-m,-(m+1)+k] \subseteq \mathrm{supp}([\mathcal{D} \setminus \{k\}])$. Thus, since $\mathrm{min}(\widetilde{[\mathcal{C} \setminus \{k\}]}) \geq \mathrm{min}(\widetilde{n\delta_0})= -m$ and $\widetilde{[\mathcal{C} \setminus \{k\}]}$ has at most one chip at each vertex, we have~$[-m,-(m+1)+k] \subseteq \mathrm{supp}(\widetilde{[\mathcal{C} \setminus \{k\}]})$. Next, note that~$[\mathcal{C}\setminus \{k\}] \lessdot [\mathcal{C}' \setminus\{k\}]$. So by applying \cref{lem:stabcover}, we conclude that $\widetilde{[\mathcal{C}\setminus \{k\}]} \lessdot \widetilde{[\mathcal{C}' \setminus\{k\}]}$, i.e., that $ \widetilde{[\mathcal{C}' \setminus\{k\}]}$ is obtained from  $\widetilde{[\mathcal{C}\setminus \{k\}]}$ by moving one chip rightward one vertex. In particular this means that we must have~$[-m,-(m+1)+k-1] \subseteq \mathrm{supp}(\widetilde{[\mathcal{C}' \setminus \{k\}]})$ (by the same reasoning as in the previous line about $ \mathrm{supp}(\widetilde{[\mathcal{C} \setminus \{k\}]}$). Now, chips~$(k)$ and~$(j)$ occupy the same vertex in~$\mathcal{C}'$, which means $[\mathcal{C}' \setminus \{k\}] = [\mathcal{C}' \setminus \{j\}]$. So by starting from $\mathcal{C}'$ and repeatedly firing all chips other than~$(j)$ until we stabilize these other chips, we can eventually reach some configuration~$\mathcal{D}'$ with $[\mathcal{D}' \setminus \{j\}] = \widetilde{[\mathcal{C}' \setminus \{j\}]} = \widetilde{[\mathcal{C}' \setminus \{k\}]}$. 

The upshot of the previous paragraph is that if the lemma is false then we can find a configuration~$\mathcal{D}'$ with~$\Delta^n \to \mathcal{D}'$ and~$[-m,-(m+1)+k-1] \subseteq \mathrm{supp}([\mathcal{D}' \setminus \{j\}])$ for some~$1 \leq j \leq k-1$. Let us show that this is impossible. For an unlabeled configuration~$c$ and $\ell \in \mathbb{Z}$, define $\varphi_{\ell}(c)  := \sum_{i \leq \ell} (i - \ell-1)\cdot c(i)$. It is easy to verify that if $c'$ is obtained from $c$ by firing at vertex $i$ then 
\[\varphi_{\ell}(c') = \begin{cases} \varphi_{\ell}(c) - 1 &\textrm{if $i = \ell+1$}; \\ \varphi_{\ell}(c) &\textrm{otherwise}. \end{cases}\]
Since $\varphi_{\ell}$ weakly decreases with each chip-firing move, we always have $\varphi_{\ell}(\widetilde{c}) \leq \varphi_{\ell}(c)$; moreover, if~$\varphi_{\ell}(c) = \varphi_{\ell}(\widetilde{c})$ then vertex $\ell+1$ never fires during the stabilization process~$c \to \widetilde{c}$. Now, we claim that~$(j)$ is strictly to the right of vertex $-(m+1)+k-1$ in~$\mathcal{D}'$: indeed, otherwise~$\varphi_{-(m+1)+k-1}([\mathcal{D}']) < \varphi_{-(m+1)+k-1}(\widetilde{[\mathcal{D}']}) = \varphi_{-(m+1)+k-1}(\widetilde{n\delta_0})$ since $[-m, -(m + 1) + k - 1] \subseteq \mathrm{supp}([\mathcal{D}' \setminus \{j\}])$. If chip~$(j)$ is strictly to the right of vertex $-(m+1)+k-1$ in~$\mathcal{D}'$, as it must be, then~$\varphi_{-(m+1)+k-1}([\mathcal{D}']) = \varphi_{-(m+1)+k-1}(\widetilde{n\delta_0})$. So if we continue to stabilize, that is, if we let $\mathcal{D}''$ be such that $\mathcal{D}' \to \mathcal{D}''$ and $\mathcal{D}''$ is stable, then the vertex $-(m+1)+k$ never fires during the labeled chip-firing process~$\mathcal{D}' \to \mathcal{D}''$. Consequently, chip~$(j)$ always remains strictly to the right of~$-(m+1)+k-1$ during the process $\mathcal{D}' \to \mathcal{D}''$. So chip~$(j)$ is strictly to the right of~$-(m+1)+k-1$ in the stable configuration $\mathcal{D}''$. But this contradicts our inductive hypothesis since $1 \leq j \leq k-1$.
\end{proof}

\begin{lemma} \label{lem:prooflem2}
Chip $(k)$ must have fired together with chip~$(k-1)$ at some point in the labeled chip-firing process $\Delta^n \to \mathcal{D}$.
\end{lemma}
\begin{proof}
Note that in the labeled chip-firing process, chips~$(k)$ and~$(k-1)$ interact in the same way with all chips~$(j)$ for~$j \neq k,k-1$. So if chip~$(k)$ and chip~$(k-1)$ never fire together in the labeled chip-firing process $\Delta^n \to \mathcal{D}$, we can swap the roles of~$(k)$ and~$(k-1)$ to reach a stable configuration $\mathcal{D}'$ where $(k)$ and $(k-1)$ have swapped places. This contradicts our inductive hypothesis which says that there is only one vertex~$(k-1)$ could end up at in a stable configuration.
\end{proof}

\cref{lem:prooflem1,lem:prooflem2} together imply that $\mathcal{D}(k) \leq -(m+1)+k$. By our inductive hypothesis, we know that vertex $-(m+1)+j$ is occupied by $(j)$ for all $1 \leq j \leq k-1$. Thus~$\mathcal{D}(k) = -(m+1)+k$. Therefore, the theorem is proved by induction.
\end{proof}

\section{Extensions}

\subsection{Other graphs}

An obvious question is if the labeled chip-firing process can be extended to other graphs beyond~$\mathbb{Z}$. While we are far from being able to propose an interesting extension of labeled chip-firing to arbitrary graphs, we have found that several minor variants of the infinite path continue to exhibit confluence of certain initial configurations. 

The first kind of variant involves adding loops to some vertices in the infinite path~$\mathbb{Z}$. For~$S \subseteq \mathbb{Z}$, let us use~$\mathbb{Z}\langle S \rangle$ to denote the graph obtained from $\mathbb{Z}$ by adding a loop at each~$i \in S$. To fire at a vertex $i \in \mathbb{Z}\langle S \rangle$ that has a loop (that is, for which $i \in S$), we now need to choose three chips $(a)$, $(b)$, and~$(c)$ which occupy~$i$. Suppose $a < b <c$; then the firing consists of moving~$(a)$ leftward one vertex and moving~$(c)$ rightward one vertex. We imagine that the middle-labeled chip~$(b)$ travels along the loop and comes back to~$i$, and so the location of~$(b)$ does not change as a result of this firing. Adding loops can certainly change which configurations stabilize uniquely: for example, $\Delta^3$ stabilizes uniquely as a configuration on~$\mathbb{Z}\langle\{0\}\rangle$, but~$\Delta^4$ does not. 

\begin{conj} \label{conj:loops}
Let $S \subseteq \mathbb{Z}$. For the purposes of this conjecture consider all configurations (labeled and unlabeled) to be on the graph~$\mathbb{Z}\langle S \rangle$. Suppose $n \in \mathbb{N}$ is such that:
\begin{itemize}
\item $\mathrm{min}(\widetilde{n\delta_0}) < \mathrm{min}(\widetilde{(n-1)\delta_0})$;
\item $\displaystyle \sum_{i \in S'} i = 0$ where $S' := S \cap [\mathrm{min}(\widetilde{n\delta_0})+1,\mathrm{max}(\widetilde{n\delta_0})-1]$.
\end{itemize}
Then $\Delta^n$ has a unique labeled stabilization.
\end{conj}

\cref{conj:loops} should follow from a minor modification of the arguments presented in the last section. Some special cases of \cref{conj:loops} are especially worth highlighting: the conjecture says that $\Delta^n$ has a unique labeled stabilization as a configuration on $\mathbb{Z}\langle \{0\} \rangle$ whenever~$n$ is odd; and the conjecture says that $\Delta^n$ has a unique labeled stabilization as a configuration on~$\mathbb{Z} \langle \mathbb{Z} \rangle$ whenever $n \equiv 3 \mod 4$.

The second kind of variant of the infinite path~$\mathbb{Z}$ involves parallel edge, but for reasons of space we will not discuss in this abstract are conjectures in this direction.

\subsection{Other configurations}

Let us use the notation $\widetilde{\mathcal{C}} := \{\mathcal{D}\colon \mathcal{C} \to \mathcal{D} \textrm{ and $\mathcal{D}$ is stable}\}$. Another natural problem is to understand $\widetilde{\mathcal{C}}$ for more configurations~$\mathcal{C}$. For example, for $n=1,3,5,7,9,\ldots$ we have $\#\widetilde{\Delta^{n}} = 1,3,12,54,232,\ldots$. Set~$n:=2m+1$. Of course $[\mathcal{D}] = [-m,m]$ for~$\mathcal{D} \in \widetilde{\Delta^{n}}$, so we may identify elements of~$\widetilde{\Delta^{n}}$ with permutations. Completely describing the permutations in~$\widetilde{\Delta^{n}}$ seems hard, but there are at least a few nontrivial things we can say. First of all, \cref{lem:labeledchippos} puts some restrictions on~$\widetilde{\Delta^{n}}$. We can also say the following: for any injective, order-preserving map~$\iota\colon [n] \to [n+1]$, if we relabel a configuration~$\mathcal{D} \in \widetilde{\Delta^{n}}$ according to $\iota$, add a new chip~$(j)$ to the origin where $\{j\} := [n+1] \setminus \mathrm{im}(\iota)$, and then stabilize the resulting configuration, the chips have to appear in sorted order. Indeed, this is a consequence of our main theorem, \cref{thm:main}, because one possible way to stabilize~$\Delta^{n+1}$ is to ignore chip~$(j)$ for as long as possible and instead first stabilize the chips with labels in~$\mathrm{im}(\iota)$. Finally, we offer the following attractive conjecture about $\widetilde{\Delta^{n}}$: the maximum number of inversions for a permutation in~$\widetilde{\Delta^{n}}$ is exactly~$m$.

A different way to understand configurations for which there is not unique labeled stabilization would be probabilistically.  There are at least three reasonable ways to carry out labeled chip-firing randomly: (1) at each step choose a chip-firing move uniformly at random among all possible moves; (2) at each step choose an unstable vertex uniformly at random and then choose a pair of chips at that vertex uniformly at random; or (3) choose a stabilization sequence uniformly at random among all (labeled) stabilization sequences.  Based on some limited computer simulations, it appears that when $m$ is large, random labeled chip-firing applied to $\Delta^{2m+1}$ leads to all chips ending up sorted with probability around $.33$, under all three protocols. We have no intuition for why this probability should not converge to 0. It is clear that it cannot converge to a limit greater than $1/3$, since $2/3$ of the time the last move fails to put the chips in sorted order. We conjecture that the probability of sorting converges to $1/3$ exactly.

\subsection{Other types}

Pavel Galashin has pointed out a compelling way to rephrase our result that situates it in a broader context. Consider the vector $v \in \mathbb{Z}^n$ that records at each step the positions of the labeled chips; the origin $(0,\dots,0)$ corresponds to the starting configuration. Firing amounts to adding the vector $e_i - e_j$ with $i < j$ to the current vector~$v$, and we are permitted to do this if and only if $e_i - e_j$ is perpendicular to $v$. These vectors are of course the positive roots of the root system of type $A_{n-1}$. Galashin's computer experiments suggests that confluence occurs for ``vector chip-firing'' in some but not all other types. For instance, in type $C_n$ it seems that confluence occurs when $n \equiv 1, 2 \mod 4$ and in type $D_n$ when $n \equiv 3 \mod 4$. And it follows from our result via symmetry that $B_n$ is confluent for \emph{all}~$n$.

\vspace{-0.5cm}

\acknowledgements{
We thank Pedro Felzenszwalb, Pavel Galashin, Caroline Klivans, Gregg Musiker, and Peter Winkler for useful comments and discussion. The first author was supported by NSF grant~\#1122374. The third author was supported by NSF grant~\#1001905.
}

\vspace{-0.5cm}

\printbibliography



\end{document}
